package A_review.review5_9;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Nqueen {


    List<List<String>>  res=new ArrayList<>();
    public   List<List<String>> solveNqueens(int n) {
        if (n<=0){
            return res;
        }
        //  CKG TODO 2023/5/9: 构造棋盘　
          char[][]  chessBoard=new char[n][n];
        for (char[]  a:chessBoard) {
            Arrays.fill(a,'.');
        }
        backTrack(chessBoard,0,n);
          return  res;
    }

    public  void  backTrack(char[][] chessBoard,int row,int n){
        //  CKG TODO 2023/5/9:
        if (row>=n){
            res.add(arratyToString(chessBoard));
            return;
        }

//        if (row==n){
//            res.add(arratyToString(chessBoard));
//            return;
//        }
        for (int col =0; col <n ; col++) {
            if (judgeChessBoard(chessBoard,row,col,n)){
                chessBoard[row][col]='Q';
                //  CKG TODO 2023/5/9: 这一块有点卡壳了
                backTrack(chessBoard,row+1,n);
                chessBoard[row][col]='.';
            }
        }
    }



    public  List  arratyToString(char[][] chessBoard){
        ArrayList<String> list = new ArrayList<>();
        for (char[] a: chessBoard) {
            //  CKG TODO 2023/5/9:  用这个方法　　用ａ．ｔｏＳｔｒｉｎｇ　不行
            list.add(String.copyValueOf(a));
        }
        return list;
    }


    public  boolean judgeChessBoard(char[][]  chessBoard,int  row,int col,int n){
        //  CKG TODO 2023/5/9: 判断列上是否有不合格的
        for (int i = 0; i < row; i++) {
            if (chessBoard[i][col]=='Q'){
                return  false;
            }
        }
        //  CKG TODO 2023/5/9: 判断对角线上是否有不合格的
        for (int i = row-1,j=col-1; i>=0&&j>=0 ; i--,j--) {
            if (chessBoard[i][j]=='Q'){
                return false;
            }
        }
        //  CKG TODO 2023/5/9: 判断右上角
        for (int i = row-1,j=col+1; i>=0&&j<n ; i--,j++) {
            if (chessBoard[i][j]=='Q'){
                return  false;
            }
        }
        return  true;
    }


}
